Recent developments in the field of computer aided modeling enable designers to manipulate representations of physical objects that have been scanned into a computer using lasers. The representation is often a two-dimensional (2-D) surface (i.e., a 2-dimensional manifold) embedded in three-dimensional (3-D) Euclidean space. The surface is constructed by collecting laser range information from various viewing angles and combining it to reconstruct the surface of the object. Initially, this surface is represented in unparameterized form. For example, a common unparameterized surface representation is a dense, seamless polygon mesh, i.e., a collection of polygons joined at their edges. This polygon mesh model of the physical object often then forms the basis for subsequent manipulation and animation. A typical model generated from 75 scans of a physical object using a laser range scanner might contain on the order of 350,000 polygons.
Dense polygon meshes are an adequate representation for some applications such as stereolithographic manufacturing or computer renderings. However, for a number of other application domains, smooth, parameterized surface representations are required in order to permit useful editing and manipulation of the surface. By smooth or parameterized surfaces we mean surfaces whose mathematical representation has a higher order mathematical property such as the existence of a global analytical derivative. In contrast to smooth surface representations, polygonal meshes are just a set of connected planar facets; they do not posses an analytical derivative.
Smooth surface representations offer useful advantages over an irregular polygonal mesh representation. Some of these advantages are:
Smooth appearance: Several applications such as consumer product design require for aesthetic reasons that 3-D surface models possess a smooth appearance. Polygonal meshes cannot be used in these applications because they may appear faceted (unless the polygons are made extremely small, which increases the expense of processing and storing the model). PA1 Compact representation: A smooth surface representation can usually represent complex surface shapes more efficiently than polygonal meshes. PA1 Flexible control: Smooth surface representations usually offer an easier interface to design, control and modify surface geometry and texture. PA1 Mathematical differentiability: Several applications use computational procedures that require the surface to be everywhere differentiable or curvature continuous (e.g., finite element analysis). For such applications, polygonal meshes cannot be used because they are merely piecewise linear surfaces. PA1 Manufacturability: Some manufacturing procedures such as CNC milling require a smooth surface representation to create high quality results. PA1 Hierarchical modeling: Creating manipulable hierarchies from smooth surfaces is a significantly simpler task than doing the same with dense, irregular, polygonal meshes.
Examples of smooth surfaces include parametric representations such as NURBS, B-spline and Bezier surfaces, implicit representations such as spheres and cylinders, algebraic representations based on explicit equations, and so on. To satisfy users that prefer or require smooth surface representations, techniques are needed for creating and fitting smooth surfaces to dense polygonal meshes.
Unfortunately, known techniques for automatically creating parameterizations often result in undesirable parameterizations. For example, it is desirable that a parameterization appropriately follow the surface contours of the mesh. To construct such parameterizations, users are currently required to manually edit the automatically created parameterization, or to specify from scratch an entire collection of isoparametric curves on the surface of the polygonal mesh. In either case, the user is faced with a labor-intensive task.